package it.storm.solution;

import java.util.*;

/**
 * 1146. 快照数组
 * https://leetcode-cn.com/problems/snapshot-array/
 */
public class Solutions_1146 {
    public static void main(String[] args) {
        // 初始化一个长度为 3 的快照数组
//        it.storm.solution.SnapshotArray snapshotArr = new it.storm.solution.SnapshotArray(1);
//        snapshotArr.set(0, 15);
//        int res1 = snapshotArr.snap();  //  output: 0
//        int res2 = snapshotArr.snap();  //  output: 1
//        int res3 = snapshotArr.snap();  //  output: 2
//        int res4 = snapshotArr.get(0, 2);  // output: 15
//        int res5 = snapshotArr.snap();  //  output: 3
//        int res6 = snapshotArr.snap();  //  output: 4
//        int res7 = snapshotArr.get(0, 0);  // output: 15
//        System.out.println("");

//        it.storm.solution.SnapshotArray snapshotArr = new it.storm.solution.SnapshotArray(1);
//        int res1 = snapshotArr.snap();  //  output: 0
//        int res2 = snapshotArr.snap();  //  output: 1
//        snapshotArr.set(0, 4);
//        int res3 = snapshotArr.snap();  //  output: 2
//        int res4 = snapshotArr.get(0, 1);  // output: 0
//        snapshotArr.set(0, 12);
//        int res5 = snapshotArr.get(0, 1);  // output: 0
//        int res6 = snapshotArr.snap();  //  output: 3
//        int res7 = snapshotArr.get(0, 3);  // output: 12
//        System.out.println("");

        SnapshotArray snapshotArr = new SnapshotArray(3);
        snapshotArr.set(1, 18);
        snapshotArr.set(1, 4);
        int res1 = snapshotArr.snap();  //  output: 0
        int res2 = snapshotArr.get(0, 0);  // output: 0
        snapshotArr.set(0, 20);
        int res3 = snapshotArr.snap();  //  output: 1
        snapshotArr.set(0, 2);
        snapshotArr.set(1, 1);
        int res4 = snapshotArr.get(1, 1);  // output: 4
        int res5 = snapshotArr.get(1, 0);  // output: 4
        System.out.println("");
    }
}

/**
 * 解题思路：只关注 index 和 snap，因为 get 时，只获取 snap_id 次快照的 index 索引上的元素
 * 定义数据结构用于记录数据的改变（以下 list 表示快照数组的长度为 3）
 * list<TreeMap<Integer, Integer>> list = new ArrayList<>();
 *  0        1        2
 * treeMap  treeMap  treeMap
 *
 * list.get(0) = TreeMap<Integer, Integer>：表示各版本号，对索引 0 做出的修改
 * TreeMap<Integer, Integer>：key：快照版本号 snap，value：set 的值
 *
 * 函数说明：
 * set(int index, int val) 时
 *  1. 修改索引 index 上的元素为 val
 *
 * snap() 时：
 *  1. 保存本次快照
 *  2. 快照版本号加 1
 *
 * get(int index, int snap_id) 时：
 *  1. 获取快照版本号为 snap_id 的数组中，索引 index 上的元素
 */
class SnapshotArray {
    int len;
    int snapId;
    List<TreeMap<Integer, Integer>> list;

    public SnapshotArray(int length) {
        len = length;
        snapId = 0;
        list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            list.add(new TreeMap<>());
        }
    }

    public void set(int index, int val) {
        TreeMap<Integer, Integer> treeMap = list.get(index);
        treeMap.put(snapId, val);
    }

    public int snap() {
        return snapId ++;
    }

    public int get(int index, int snap_id) {
        TreeMap<Integer, Integer> treeMap = list.get(index);
        // 获取小于等于 snap_Id 的最大值
        Map.Entry<Integer, Integer> entry = treeMap.floorEntry(snap_id);
        if (entry == null) {
            // 说明快照版本号 snap_id 未对索引 index 作出改变
            return 0;
        }
        return entry.getValue();
    }
}